package leetcode.p28;

/**
 * @author: trtan
 * @create: 2021-04-20 12:47
 * @description:
 **/
public class KMP {
    public static void main(String[] args) {
        System.out.println(new KMP().strStr("hello", "ll"));
    }
    public void getNext(int[] next, String patten) {
        char[] chars = patten.toCharArray();
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < chars.length; i++) {
            while (j > 0 && chars[i] != chars[j]) {
                j = next[j - 1];
            }
            if (chars[i] == chars[j]) {
                j++;
            }
            next[i] = j;
        }
    }

    public int strStr(String str, String patten) {
        if ("".equals(patten) || patten == null) {
            return 0;
        }
        int[] next = new int[patten.length()];
        getNext(next, patten);
        char[] pattens = patten.toCharArray();
        char[] chars = str.toCharArray();
        int j = 0;
        for (int i = 0; i < chars.length; i++) {
            while (j > 0 && chars[i] != pattens[j]) {
                j = next[j - 1];
            }
            if (chars[i] == pattens[j]) {
                j++;
            }
            if (j == pattens.length) {
                return i - j + 1;
            }
        }
        return -1;
    }
}
